#include <iostream>
#include <climits>
#include <vector>
#include <LEDA/numbers/fp.h>
#include <LEDA/graphics/graphwin.h>
#include <LEDA/graphics/color.h>
#include <LEDA/core/set.h>
#include <LEDA/core/queue.h>
#include <LEDA/core/p_queue.h>
#include <LEDA/graphics/window.h>
#include <LEDA/graph/graph.h>
#include "control.h"

#include <cmath>

#define INF -1

using namespace leda;


/**
 * Get edge weight of a given edge e
 */
int get_edge_weight(GraphWin &gw , edge &e)
{
	string edge_label = gw.get_user_label(e);
	int weight = atoi(edge_label.c_str());
	return weight;
}

/**
 * Dijkstra's algorithm to compute shortest paths in a directed graph.
 */
void dijkstra(node &start , graph &g, GraphWin &gw , node_array<int> &dist , node_array<edge> &from)
{

	// distance from source to source
	dist[start] = 0;
	gw.set_user_label(start , string("%i" , 0));

	//store all pq_items for quick access for updates etc.
	node_array<bin_heap_item> node_pq_pointer(g , NULL);

	//marks the presence of a node in the tree
	node_array<bool> marker(g, false);

	//priority queue for all nodes adjacent to our tree
	p_queue<double, edge> priority_queue;

	edge e_iter;

	forall_out_edges(e_iter, start) {
		//insert the edge into the priority queue
		bin_heap_item it = priority_queue.insert(get_edge_weight(gw, e_iter) , e_iter);
		//save the pq_item in a map for quick access through the target node
		node target = g.opposite(e_iter, start);
		node_pq_pointer[target] = it;
		//node start is the first node in our tree. Therefore we mark it as visited.
		marker[start] = true;
	}

	//pop edges from the priority queue and add them to our tree.
	//after that check all its neighbors and update the priority queue

	while(!priority_queue.empty())
	{
		edge e = priority_queue.inf(priority_queue.find_min());
		double path_length = priority_queue.prio(priority_queue.find_min());

		// delete item from priority queue
		priority_queue.del_min();

		//see which side of the edge is not yet marked
		node target = g.opposite(target, e);
		if (marker[target])
		{
			target = g.opposite(target, e);
		}

		// mark target as visited
		marker[target] = true;

		dist[target] = path_length;
		from[target] = e;

		gw.set_user_label(target , string("%i" , dist[target]));

		// unset the pointer from target to its pq_item (it is gone anyway)
		node_pq_pointer[target] = NULL;

		// now we need to update the priority queue with the neighbors of target
		edge adj_edge;

		forall_out_edges(adj_edge, target)
		{
			node neighbour = g.opposite(adj_edge, target);

			// ignore self-loops and nodes that are marked
			if ((neighbour != target) && (!marker[neighbour]))
			{
				// get the priority queue item.
				bin_heap_item node_item = node_pq_pointer[neighbour];

				double new_distance = dist[target] + get_edge_weight(gw , adj_edge);
				// if item exists check if we have to update it
				// else we add a new item to the list
				if (node_item != NULL)
				{
					if (priority_queue.prio(node_item) > new_distance)
					{
						// replace the current edge with the 'better' edge
						priority_queue.change_inf(node_item, adj_edge);
						priority_queue.decrease_p(node_item, new_distance);
					}
				}
				else
				{
					// if the node is not yet in our queue we add it
					// and add the reference in the node_pq_pointer map
					bin_heap_item new_item = priority_queue.insert(new_distance, adj_edge);

					node_pq_pointer[neighbour] = new_item;

				}

			} // end if (neighbor != target && !marker[neighbor])

		} // end forall_inout_edges

	} // end while

}

// Show current state of matching
void show_pure_matching(
		GraphWin &gw ,
		graph &g ,
		edge_array<int> &original_weights ,
		edge_array<bool> &matched_edges,
		node &S_node,
		node &T_node,
		edge_array<int> &current_weights
	) {

	edge e;

	g.hide_node(S_node);
	g.hide_node(T_node);

	//hide all outgoing edges from S_node
	forall_out_edges(e , S_node) {
		g.hide_edge(e);
	}
	// hide all incoming edges to T_node
	forall_in_edges(e , T_node) {
		g.hide_edge(e);
	}

	gw.update_graph();

	gw.set_directed(false);

	node v;
	//Clean up edge coloring, reset to pure matching
	forall_nodes(v , g) {
		gw.set_user_label(v , "");
		gw.set_color(v , grey3);
	}

	forall_edges(e , g) {
		//check if current edge is an old edge. If not, display 'real' weight of edge and save current one
		if (!(g.source(e) == S_node || g.target(e) == T_node )){
			current_weights[e] = get_edge_weight(gw , e);
			gw.set_user_label(e , string("%i" , original_weights[e]));
		}

		if (!matched_edges[e]) {
			gw.set_color(e , grey3);
		} else {
			gw.set_width(e , 3);
			gw.set_color(e , blue);
		}

		gw.set_style(e , solid_edge);
	}
	gw.update_graph();

}

/**
 * Show algorithm view
 */
void show_algorithm_view(GraphWin &gw , graph &g , node &S_node , node &T_node , edge_array<int> &current_weights) {
	edge e;
	forall_edges(e , g) {
	//check if current edge is an old edge. If not, display 'real' weight of edge and save current one
		if (!(g.source(e) == S_node || g.target(e) == T_node )){
			gw.set_user_label(e , string("%i" , current_weights[e]));
		}
		gw.set_width(e , 1);
	}
		gw.update_graph();



		gw.del_message();

		g.restore_all_nodes();
		g.restore_all_edges();

		gw.update_graph();
		gw.set_directed(true);
}


/*
 * 	Get a call_stack (alternating path) and augment it
 *
 */
bool augment(
		GraphWin &gw ,
		graph &g ,
		node_array<int> &dist ,
		node_array<edge> &from,
		node &S_node,
		node &T_node,
		set<edge> &original_edges,
		edge_array<int> &original_weights,
		edge_array<bool> &matched_edges,
		int &matching_cardinality,
		int &matching_size)
{

	//we did not find a path from S_node to T_node => There is no path
	if (dist[T_node] == INT_MIN) {
		return false;
	}

	gw.message("Dijkstra phase done. Augmenting path from T to S");

	node current_node;

	edge e;

	current_node = T_node;


	matching_cardinality++;

	edge_array<bool> done(g , false);

	while (current_node != S_node && current_node != NULL) {

		e = from[current_node];

		done[e] = true;

		if (original_edges.member(e)){
			//edge was part of original graph. invert it
			//currently unmatched => match it!
			if (!matched_edges[e]) {
				matched_edges[e] = true;

				//add edge size to current matching size
				matching_size += original_weights[e];

				gw.set_width(e , 2);
				gw.set_color(e , blue);
				gw.set_style(e , solid_edge);
			} else { //matched => unmatch!
				matched_edges[e] = false;

				//remove edge size from current matching size
				matching_size -= original_weights[e];

				gw.set_width(e , 1);
				gw.set_color(e , grey3);
				gw.set_style(e , solid_edge);
			}
			gw.update_graph();
			control_wait(1);

			//next, revserse edge
			g.rev_edge(e);

			//graph was changed, tell GraphWin to update window
			gw.update_graph();

			//set new edge weight 0
			gw.set_label(e , "0");
			gw.update_graph();

			//edge done, move one node up in path
			current_node = g.opposite(e , current_node);

		} else {
			// edge not part of original graph. Ignore edge, just set current node
			current_node = g.opposite(e , current_node);
			g.del_edge(e);
			gw.update_graph();
		}

	}

	gw.del_message();
	gw.message("Updating edge weights of edges that are not part of the augmenting path.");
	//calculate new edge weights for edges that are not in the path
	forall_edges(e , g) {
		//if edge was not part of augmenting path, update edge weight
		if (!done[e]) {
			//mark edge as active
			gw.set_color(e , red);
			control_wait(0.25);

			node source = g.source(e);
			node target = g.target(e);

			int new_edge_weight = get_edge_weight(gw , e);

			//Make suretarget / source was reachable. If so update edge weight.
			if (dist[target] != INT_MIN)
				new_edge_weight -= dist[target];

			if (dist[source] != INT_MIN)
				new_edge_weight += dist[source];

			//set new edge weight for edge e
			gw.set_user_label(e , string("%i" , new_edge_weight));
			gw.update_graph();
			control_wait(1);
			//mark edge as inactive
			gw.set_color(e , grey3);
		}
	}
	control_wait(1);

	gw.del_message();
	return true;
}

/**
 * Clear the graph, color everything grey
 */
void clear_graph(GraphWin &gw , graph &g) {
	edge e;

	forall_edges(e,g) {
		gw.set_width(e , 1);
		gw.set_style(e , solid_edge);
		gw.set_color(e , grey3);
		gw.set_color(g.source(e) , grey3);
		gw.set_color(g.target(e) , grey3);
		gw.update_graph();
	}

}

/**
 * Colors all edges on the path from T_node to S_node
 */
void mark_path(graph &g, GraphWin &gw , node_array<edge> &from , node &T_node) {
	edge e;
	node current_node;

	current_node = T_node;

	while (current_node != NULL) {
		e = from[current_node];
		if(e != NULL) {
			gw.set_color(e , green);
			current_node = g.opposite(e , current_node);
		} else {
			break;
		}
	}

}


void weighed_bipartite_matching(GraphWin &gw , graph &g , int &running_type) {


    /* V1 and V2 are the partitions of the graph */
    set<node> V1, V2;
    set<edge> original_edges;

    edge_array<int> original_weights(g , 0);

    // the minimum negative value in the graph
    int min_neg_value = 0;
    // the minimum positive value in the graph
    int max_pos_value = 0;

    //color all edges and nodes grey
    edge e;
    forall_edges(e, g)
    {
    	node v = g.target(e);
    	node s = g.source(e);

    	gw.set_color(e, grey3);
    	gw.set_color(v , grey3);
    	gw.set_color(s , grey3);

    	int weight = get_edge_weight(gw , e);

    	original_weights[e] = weight;
    	original_edges.insert(e);

    	gw.set_user_label(e,string("%d", weight));

        // add target vertices to the corresponding graph partition ( V1 V2 )
    	if(atoi(gw.get_user_label(v).c_str()) == 1){ // if label 1 add them to V1
    		V1.insert(v);
    	}
    	else if (atoi(gw.get_user_label(v).c_str()) == 2){ // if label 2 add them to V2
    		V2.insert(v);
    	}
        // add source vertices to the corresponding graph partition ( V1 V2 )
    	if(atoi(gw.get_user_label(s).c_str()) == 1){ // if label 1 add them to V1
    		V1.insert(s);
    	}
    	else if (atoi(gw.get_user_label(s).c_str()) == 2){ // if label 2 add them to V2
    		V2.insert(s);
    	}


    	// set width of the edge according to their weight
    	if (weight > 0) {
    		// get the smallest negative value in the graph
    		max_pos_value = max_pos_value > weight
    						? max_pos_value
    						: weight;
    	}
    	// if negative weight, set the style to dashed, min_neg_value will be the smallest negative weight
    	else {
//    		gw.set_color(e , red);

    		// get the smallest negative value in the graph
    		min_neg_value = min_neg_value < weight
    						? min_neg_value
    						: weight;
    	}
    	// set edge and vertice color

        gw.set_label_type(v, user_label);
        gw.set_label_type(s, user_label);
    }




   if (running_type == 1) //Minimal
   {
	    forall_edges(e, g)
		{
	    	int weight = get_edge_weight(gw , e);
	    	// current value plus the absolute value of the min neg value
	    	gw.set_user_label(e,string("%i", weight + abs(min_neg_value)));
	    	gw.update_graph();
		}
   }
   else if (running_type == 2) //Maximal
   {
	    forall_edges(e, g)
		{
	    	int weight = get_edge_weight(gw , e);
	    	// current negated value plus the max pos value
	    	gw.set_user_label(e,string("%i", - weight + abs(max_pos_value)));
	    	gw.update_graph();
		}
   }



   // Source and Target nodes added to G

   point p2 = point((gw.get_xmin() + gw.get_xmax() ) /2 ,gw.get_ymin()+1);
   point p = point((gw.get_xmin() + gw.get_xmax() ) /2 ,gw.get_ymax()-1);

   node S_node = gw.new_node(p);
   node T_node = gw.new_node(p2);

   gw.set_label_type(S_node , user_label);
   gw.set_label_type(T_node , user_label);

   gw.set_user_label(S_node , string("S"));
   gw.set_user_label(T_node , string("T"));

   gw.update_graph();


   node v;
   // connect Source node with the nodes from V1
   forall(v , V1) {
	   edge e = gw.new_edge(S_node, v);
	   gw.set_label(e , "0");
   }

   // connect Target node with the nodes from V2
   forall(v , V2) {
	   edge e = gw.new_edge(v, T_node);
	   gw.set_label(e , "0");
   }

   gw.update_graph();

   //dijkstra phase

   gw.set_directed(true);

   edge_array<bool> matched_edges(g , false);


   node_array<int> dist(g,INT_MIN);
   node_array<edge> from(g,NULL);

   int matching_cardinality = 0;
   int matching_size = 0;

   do {
	   edge_array<int> current_weights(g , 0);
	   //show matching
	   show_pure_matching(gw, g , original_weights , matched_edges , S_node , T_node, current_weights);

	   gw.message("Showing current state of matching.");
	   control_wait(3);

	   //hide matching (show s, t, and directed edges)
	   show_algorithm_view(gw, g, S_node , T_node , current_weights);
	   gw.update_graph();

	   dist = node_array<int>(g,INT_MIN);
	   from = node_array<edge>(g,NULL);

	   gw.message("Starting Dijkstra phase.");
	   dijkstra(S_node , g , gw , dist , from);

	   gw.del_message();
	   clear_graph(gw, g);
	   gw.message("Showing path from S to T if existent.");
	   mark_path(g, gw, from , T_node);
	   control_wait(3);

	   gw.del_message();

	   gw.update_graph();

   } while (augment(gw , g , dist , from , S_node ,  T_node , original_edges ,original_weights,
		   matched_edges , matching_cardinality , matching_size) );


   gw.message(string("Size: %i ; Weight: %i" , matching_cardinality , matching_size));
   edge_array<int> current_weights(g , 0);
   //show matching
   show_pure_matching(gw, g , original_weights , matched_edges , S_node , T_node, current_weights);



}



int main(int argc, char *argv[]) {

	window *MaxMinWindowP;
    GraphWin gw(800, 600);
    gw.display();
    create_control();
    gw.set_directed(false);

    if (argc > 1)
        gw.read(argv[1]);
    gw.edit();
    graph &g = gw.get_graph();
    if (g.number_of_nodes() == 0) {
        gw.close(); destroy_control();
        exit(1);
    }

    // Reading the running type, maximal or minimal weighted matching
    MaxMinWindowP = new leda::window(260, 40, "Running type");
    MaxMinWindowP->buttons_per_line(2);
    MaxMinWindowP->button("Minimal",  1);
    MaxMinWindowP->button("Maximal",  2);
    MaxMinWindowP->display(0, 120);
    int running_type = MaxMinWindowP->read_mouse();
    MaxMinWindowP->close();


    weighed_bipartite_matching(gw , g , running_type);


    gw.acknowledge("Ready!");
    gw.edit();
    gw.close();
    destroy_control();
    delete MaxMinWindowP;
    exit(0);
}
